#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long LL;
const LL MOD=7528443412579576937;
LL mul(LL a,LL b)
{
	LL ans=0;
	for(;b;b>>=1,a=(a+a)%MOD)
		if(b&1)ans=(ans+a)%MOD;
	return ans;
}
struct Matrix
{
	LL num[3][3];
	Matrix operator *(const Matrix a)const
	{
		Matrix ans;
		memset(ans.num,0,sizeof(ans.num));
		for(LL i=1;i<=2;++i)
			for(LL j=1;j<=2;++j)
				for(LL k=1;k<=2;++k)
					ans.num[i][j]=(ans.num[i][j]+mul(num[i][k],a.num[k][j]))%MOD;
		return ans;
	}
};
int main()
{
	LL b,d,n;
	scanf("%llu%llu%llu",&b,&d,&n);
	Matrix a,ans;
	a.num[1][1]=b;
	a.num[1][2]=1;
	a.num[2][1]=(d-b*b)/4;
	a.num[2][2]=0;
	ans.num[1][1]=b;
	ans.num[1][2]=2;
	ans.num[2][1]=ans.num[2][2]=0;
	if(!n)
	{
		printf("1\n");
		return 0;
	}
	LL nn=n-1;
	for(;nn;nn>>=1,a=a*a)
		if(nn&1)ans=ans*a;
	if(b*b!=d&&n%2==0)ans.num[1][1]=(ans.num[1][1]+MOD-1)%MOD;
	printf("%llu\n",ans.num[1][1]%MOD);
	return 0;
}
